//地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外）
//，也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。
//但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
//示例 1：
//输入：m = 2, n = 3, k = 1
//输出：3
//示例 2：
//输入：m = 3, n = 1, k = 0
//输出：1
//提示：
//1 <= n,m <= 100
//0 <= k<= 20

package main

import "fmt"

func dsf(site [][]int, m int, n int, k int, x int, y int, res *int) {
    site[x][y]=1  // 访问过的节点，做好标记
	if x/10+x%10+y%10+y/10 <= k {
		*res++ // 满足条件 +1
	}else{
		return // 不满足不再向下检索了，停止递归和使用了
	}
	//if x-1>-1 && site[x-1][y]!=1{
	//	dsf(site, m, n, k, x-1, y, res)
	//}
	if x+1 < m && site[x+1][y] != 1 {
		dsf(site, m, n, k, x+1, y, res)
	}
	if y+1 < n && site[x][y+1] != 1 {
		dsf(site, m, n, k, x, y+1, res)
	}
	//if y-1>-1  && site[x][y-1] != 1 {
	//	dsf(site, m, n, k, x, y-1, res)
	//}
}

func movingCount(m int, n int, k int) int {
	res := 0
	site := make([][]int, m)
	for i, _ := range site {
		site[i] = make([]int, n)
	}
	x := 0
	y := 0
	site[0][0] = 1
	dsf(site, m, n, k, x, y, &res)
	return res
}
func main() {
	fmt.Println(movingCount(16, 8, 4))
}
